package solution;


import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Vector;

import jigsaw.Jigsaw;
import jigsaw.JigsawNode;


/**
 * 在此类中填充算法，完成重拼图游戏（N-数码问题）
 */
public class Solution extends Jigsaw {

	private List<JigsawNode> solutionPath; 	// 解路径
	private int searchedNodesNum;           // 已访问节点数：用以记录所有访问过的节点的数量

	private Queue<JigsawNode> exploreList;
	private Queue<JigsawNode> visitedList;
	
	/**
     * 拼图构造函数
     */
    public Solution() {
    }

    /**
     * 拼图构造函数
     * @param bNode - 初始状态节点
     * @param eNode - 目标状态节点
     */
    public Solution(JigsawNode bNode, JigsawNode eNode) {
        super(bNode, eNode);
    }

    /**
     *（实验一）广度优先搜索算法，求指定5*5拼图（24-数码问题）的最优解
     * 填充此函数，可在Solution类中添加其他函数，属性
     * @param bNode - 初始状态节点
     * @param eNode - 目标状态节点
     * @return 搜索成功时为true,失败为false
     */
    public boolean BFSearch(JigsawNode bNode, JigsawNode eNode) {
    	this.beginJNode = new JigsawNode(bNode);
        this.endJNode = new JigsawNode(eNode);
        
        this.currentJNode = new JigsawNode(bNode);
        
        this.exploreList = new LinkedList<JigsawNode>();
        this.visitedList = new LinkedList<JigsawNode>();
        
        // first node enter the queue
        exploreList.offer(this.beginJNode);
        
        while (!this.exploreList.isEmpty()) {

        	currentJNode = exploreList.peek();
			
        	
        	if(currentJNode.equals(endJNode)) {	// find the solution
        		this.visitedList.offer(currentJNode);
        		this.searchedNodesNum++;
        		this.solutionPath = getPath();        		
                break;
			}else {				
        		visitedList.offer(currentJNode);
        		  		
        		/* judge whether the four direction is valid
        		 * four direction means four nextNode
        		 */
        		for(int i = 0; i < 4; i++) {
        			JigsawNode nextNode = new JigsawNode(this.currentJNode);
        			if(nextNode.move(i)
        					&& !this.visitedList.contains(nextNode) 
                			&& !this.exploreList.contains(nextNode)) {
        				this.exploreList.offer(nextNode);
        			}
        		}        		

                /* access the nextNode              
                 */
                this.exploreList.poll();
                this.currentJNode = this.exploreList.peek();
                this.searchedNodesNum++;
			}
		}
        
        System.out.println("Jigsaw BFSearch Result:");
        System.out.println("Begin state:" + bNode.toString());
        System.out.println("End state:" + eNode.toString());
        System.out.println("Total number of searched nodes:" + this.searchedNodesNum);
        System.out.println("Depth of the current node is:" + this.getCurrentJNode().getNodeDepth());
        
        return isCompleted();
    }


    /**
     *（Demo+实验二）计算并修改状态节点jNode的代价估计值:f(n)
     * 如 f(n) = s(n). s(n)代表后续节点不正确的数码个数
     * 此函数会改变该节点的estimatedValue属性值
     * 修改此函数，可在Solution类中添加其他函数，属性
     * @param jNode - 要计算代价估计值的节点
     */
    public void estimateValue(JigsawNode jNode) {
        int s = 0; // 后续节点不正确的数码个数
        int dimension = JigsawNode.getDimension();
        for (int index = 1; index < dimension * dimension; index++) {
            if (jNode.getNodesState()[index] + 1 != jNode.getNodesState()[index + 1]) {
                s++;
            }
        }            

        /*
         *  Manhattan Distance
         *  The distance between each incorrect loc and each correct loc
         */
        int currenttoStartDis = 0;
        int manhattanDis = 0;
        // add weight 
        int EuclideanDis = 0;
        
        // calculate the distance between currentNode and startNode
        for(int i = 1; i < dimension * dimension; i++) {
        	for(int j = 1; j < dimension * dimension; j++) {
        		// current Node
        		int currentNode = jNode.getNodesState()[i];
        		int startNode = beginJNode.getNodesState()[j];
        		if (currentNode == startNode && currentNode != 0) {
        			/* currentNode's X and Y
        			 * X: row of puzzle
        			 * Y: col of puzzle
        			 */
        			int cX = (i - 1) / dimension;
        			int cY = (i + 4) % dimension;
        			        			
        			// starttNode's X and Y
        			int sX = (j - 1) / dimension;
        			int sY = (j + 4) % dimension;
        			
        			int dX = Math.abs(sX - cX);
        			int dY = Math.abs(sY - cY);
        			
        			currenttoStartDis += (dX + dY);
        			//EuclideanDis += (int)(Math.sqrt(dX * dX + dY * dY));
        			break;
				}
        	}
        }
        
        // calculate Manhattan Distance
        for(int i = 1; i < dimension * dimension; i++) {
        	for(int j = 1; j < dimension * dimension; j++) {
        		// current Node
        		int currentNode = jNode.getNodesState()[i];
        		int targetNode = endJNode.getNodesState()[j];
        		if(currentNode == targetNode && currentNode != 0) {
        			/* currentNode's X and Y
        			 * X: row of puzzle
        			 * Y: col of puzzle
        			 */
        			int cX = (i - 1) / dimension;
        			int cY = (i + 4) % dimension;
        			        			
        			// targetNode's X and Y
        			int tX = (j - 1) / dimension;
        			int tY = (j + 4) % dimension;
        			
        			int dX = Math.abs(tX - cX);
        			int dY = Math.abs(tY - cY);
        			
        			manhattanDis += (dX + dY);
        			//EuclideanDis += (int)(Math.sqrt(dX * dX + dY * dY));
        			break;
        		}        		
        	}
        }
        
        //currenttoStartDis = 0;
        //System.out.println(currenttoStartDis);
        
        int estimate = manhattanDis * 2 + s + currenttoStartDis;//+ EuclideanDis; 
        jNode.setEstimatedValue(estimate);        
    }
}
